package com.algorithm.cjm.csnote

import java.util.*

/**
 * 二叉树
 *
 * 用链表来构建二叉树，
 *
 *
 * Created by jieming.chen on 2021/2/11
 */

data class TreeNode(val data: Int,
                    var leftChild: TreeNode? = null,
                    var rightChild: TreeNode? = null)

fun createBinaryTree(inputList: LinkedList<Int>?): TreeNode? {
    var node: TreeNode? = null
    if (inputList == null || inputList.isEmpty()) {
        return null
    }
    val data = inputList.removeFirst()
    if (data != null) {
        node = TreeNode(data)
        node.leftChild = createBinaryTree(inputList)
        node.rightChild = createBinaryTree(inputList)
    }
    return node
}

fun preOrderTraveral(node: TreeNode?) {
    if (node == null) {
        return
    }
    print("${node.data} ")
    preOrderTraveral(node.leftChild)
    preOrderTraveral(node.rightChild)
}

fun inOrderTraveral(node: TreeNode?) {
    if (node == null) {
        return
    }
    inOrderTraveral(node.leftChild)
    print("${node.data} ")
    inOrderTraveral(node.rightChild)
}

fun postOrderTraveral(node: TreeNode?) {
    if (node == null) {
        return
    }
    postOrderTraveral(node.leftChild)
    postOrderTraveral(node.rightChild)
    print("${node.data} ")
}

// 用栈的方式遍历
fun preOrderTraveralWithStack(root: TreeNode?) {
    val stack = Stack<TreeNode>()
    var treeNode = root
    while (treeNode != null || !stack.isEmpty()) {
        while (treeNode != null) {
            print("${treeNode.data} ")
            stack.push(treeNode)
            treeNode = treeNode.leftChild
        }
        if (!stack.isEmpty()) {
            treeNode = stack.pop()
            treeNode = treeNode.rightChild
        }
    }
}

fun main(args: Array<String>) {
    val linkedList = LinkedList<Int>(listOf(3, 2, 9, null, null, 10, null, null, 8, null, 4))
    val createBinaryTree = createBinaryTree(linkedList)

    preOrderTraveral(createBinaryTree)
    println()
    inOrderTraveral(createBinaryTree)
    println()
    postOrderTraveral(createBinaryTree)
    println()
    preOrderTraveralWithStack(createBinaryTree)
}
